# LeetCode 53. 最大子数组和
# https://leetcode.cn/problems/maximum-subarray/description/
from typing import List


# 分治
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        result = self.bisect(nums, 0, len(nums) - 1)
        return result

    def bisect(self, nums, left, right):
        if left == right:
            return nums[left]
        mid = (left + right) // 2
        left_max = self.bisect(nums, left, mid)
        right_max = self.bisect(nums, mid + 1, right)

        tmp = 0
        left_nums = nums[left: mid + 1]
        max_l = left_nums[-1]
        for i in range(len(left_nums) - 1, -1, -1):
            tmp += left_nums[i]
            max_l = max(max_l, tmp)

        tmp = 0
        right_nums = nums[mid + 1: right + 1]
        max_r = right_nums[0]
        for i in range(len(right_nums)):
            tmp += right_nums[i]
            max_r = max(max_r, tmp)

        return max(left_max, right_max, max_l + max_r)


# 暴力 不超时
# class Solution:
#     def maxSubArray(self, nums: List[int]) -> int:
#         result = nums[0]
#         tmp_sum = nums[0]
#         for i in range(1, len(nums)):
#             if tmp_sum + nums[i] >= nums[i]:
#                 tmp_sum += nums[i]
#                 result = max(tmp_sum, result)
#             else:
#                 result = max(tmp_sum, result, nums[i])
#                 tmp_sum = nums[i]
#
#         return result


# O(n)
class Solution2:
    def maxSubArray(self, nums: List[int]) -> int:
        tmp_sum, result = 0, 0
        for index, num in enumerate(nums):
            tmp_sum = max(tmp_sum + num, num)
            result = max(tmp_sum, result)
        return result


if __name__ == '__main__':
    nums = [-2,1,-3,4,-1,2,1,-5,4]
    result = Solution().maxSubArray(nums)
    print(result)

    result2 = Solution2().maxSubArray(nums)
    print(result2)
